\section{The Proposed Methodology and Mechanism}
Known-Good-Die(KGD) test is commonly used in System-in-Package (SIP) testing flow. Chips with different functionality, for example, processor, DRAM, RF chips, can be packaged together using wire bounding or other package technologies. The difference of SIP testing and TSV-based 3D IC testing is that each die in a SIP has separate pads. These dies could be probed and functional test can be performed independently before packaging. It is not easy to perform KGD test for TSV-based 3D stacking, because typically only one 3D stacking tier carries all the system pads and the input and output pins of other tiers are exploded without ESD protection before stacking.
On the other hand, the TSV defect rate could be much higher than that of wire bonding in normal SIP flow.
In this section, we describe our proposed methodology and mechanism.

\subsection{Time-Efficient Testing Flow}

TSV-based 3D integration has three stacking methods: face-to-face, face-to-back and back-to-back. Our proposed methodology targets at the die-stacking method with face-to-back stacking for all tiers, except for the last tie, which uses face-to-face stacking, as illustrated in Figure~\ref{fig:1}.  The pads on the bottom layer is connect to package from backside through TSV, so that the face to face metal resource can be reserved for inter-tier connection.

Our testing flow can be divided into two stages. 

%\noindent$\bullet$\textbf{Stage I:} the TSV only testing and apply
%redundancy.

%\noindent$\bullet$\textbf{Stage II:} the internal circuit function
%test. 

\textbf{Stage I:}  Test the TSVs only and apply redundancy to fix defected TSVs.

\textbf{Stage II:} Test the internal circuit function. 

The testing begins with tier 0 and follows these two testing stages. Stage I is performed first and Stage II is applied only after passing stage I. These two stages contribute to the test time separately. After finishing the test on tier 0, tier 1 is tested in the same way, and so on. In our targeted stacking structure (as shown in Figure 1), the last tier (Tier N) has no TSVs and uses top metal layer for inter-tie connection. Therefore, Tier N can skip the stage I. Usually, the normal CMOS process has pretty high yield, while the TSV yield still need to be improved~\cite{Jing:IMEC}. Testing time is a key factor of testing cost~\cite{Jing:testbook}. Finding those TSV defects earlier can optimize the total testing time and reduce testing cost. The tier stacking method in Figure~\ref{fig:1} shows that the BIST logics on each of the tiers to perform TSV self-test, whose structures will be discussed in next section.

The detail testing flow in Figure~\ref{fig:2} is a modified Known-Good-Stack (KGS) testing strategy to increase yield. The logic testing method for 3D ICs has been discussed in prior work~\cite{Jing:Xiaoxia}. Our flow can use any existing logic testing methods for circuit testing. Our design focus on searching defect TSVs and applying redundancy. Such flow can increase the yield from two aspects: (1) no tiers will be stacked on defected chips; (2) using the testing result to config the TSV replacement circuit.

\begin{figure}[t]
\centering
\includegraphics[width=0.5\textwidth]{figure/fig1_3DIC}
\caption{\small{Die stacking scheme and test order.}}
\label{fig:1}
\end{figure}

\begin{figure}[t]
\centering
\includegraphics[width=0.45\textwidth]{figure/2flow}
\caption{\small{Timing efficient stacking and test flow. N is the number of 3D stacking layers.}}
\label{fig:2}
\end{figure}

\subsection{Circuit Level Consideration of Design for Testing}

There are two TSV placement methods: the arbitrary pattern and the TSV cluster. The arbitrary placement provides more design flexibility, but recent research shows that the arbitrary placement is more vulnerable to TSV mechanical stress, which can result in TSV reliability issues~\cite{TSVstress} and affect the nearby CMOS device mobility~\cite{TSVmobility}. As a result,
we focus on TSV clustering design in this work.

The testing circuit configuration of an $N\times{N}$ TSV cluster is illustrated in Figure~\ref{fig:3}. A MUX-based test chain connects all the TSVs to the test block. During testing, the input signal is generated with a 50\% duty cycle pulse. When all the TSVs in a testing chain are functioning, the test block receives a flipping signal. In testing mode, the select signals $<s0:sn>$ determine which part of the TSV chain is under test. 
%The MUXs under control have power source. They are active drivers, which can propagate the signal to output without decay. 
The $in$ testing signal can be generated on chip with changeable frequency. Since this pulse input does not carry any data information, it can be fast and reach $GHz$, which is much faster than scan-in speed.  Therefore, in test time discussion, one cycle or one testing cycle is not the pulse cycle time, but stands for the time to finish the test under one select signal $<s0:sn>$ configuration. In operation mode, the MUXs should not affect the data signals carried by TSVs. Hence, there are transmission gates inside the MUXs to disconnect them from TSVs, when necessary.

TSV delay under recent technology is less than 10 FO4. The testing signal can pass through each TSV in one pulse cycle. If one or more TSVs are affected by large variation or have defects, their RC delay may be larger than good TSVs. When such delay excesses one pulse cycle, the $out$ signal stops flipping, because the defect TSV output could not reach a threshold before the input signal changes.  The electric model of a TSV is similar to a long metal wire~\cite{tsvmodel}. Its equivalent circuit is shown in Figure~\ref{fig:tsv}, where each TSV has its own driving cell. The large side-wall capacitance makes it a heavy load for the driving cell. The signal transmitted through it experiences a relatively long delay.

We use TSV delay to distinguish defects. Such defects can be detected by changing the pulse frequency. The TSV delay also depends on its driving cell size, which should be small intentionally to sense the frequency change. Thus the carefully sized testing circuits do not have large area overhead comparing with the TSV area.

There are testing circuit on both tiers to test the TSV defects together.  For example, The black tier (tier 1 in Figure~\ref{fig:3}) is closer to the bottom tier and has already been tested. In this tie, all the input signals are reliable. The grey tier (tier 2) is the upper tie. The TSV under test belongs to \emph{tier 2} and all the signals in \emph{tier 2} cannot be trusted yet. The $ctrl$ signals of the transmission gate on tier 2 are set to be 1 as long as the upper layer is powered on. According to today's TSV yields, many TSV design rules require to group two TSVs together to transfer one signal. Accordingly, our testing circuit will testing two TSVs as a group. The testing result only shows whether a two-TSV group has defect. If these two TSVs need to transfer different signals, transmission gate will be turned off during chip operation. 
%However, in the testing stage, they cannot be distinguished.

The test block has three functions: (1) monitoring the $out$ signal to check whether it is flipping; (2) generating the select signal to control the TSV cluster
MUX. In this way, the tested TSVs group can be excluded from the chain; (3) providing defect information in the TSV cluster, which will be used locally to apply redundancy.
The testing block senses if the $out$ signal is flipping every test cycle, which is much longer than the pulse cycle. Therefore a long testing chain will not violate any timing constraint.

\begin{figure}
\centering
\includegraphics[width=0.5\textwidth]{figure/4flow}
\caption{\small{TSV test chain. One cluster of TSVs are connected
    together by MUX and FF. The Test Block will generatea the select
    signal of all the MUX and result of defect TSV locations. }}
\label{fig:3}
\end{figure}

\begin{figure}
\centering
\includegraphics[width=0.5\textwidth]{figure/tsv}
\caption{\small{TSV circuit model}}
\label{fig:tsv}
\end{figure}

\subsection{Yield Modeling and Defect Searching Algorithm}

TSV redundancy can improve chip yield by replacing the failed TSVs with nearby redundant TSV resources. At the design stage, a BIST scheme can be implemented after the number and the location of the redundant TSVs are decided. A yield model is introduced in this design for estimating the number of extra TSVs required. After that, a breadth-first binary search method is used to find the failed TSVs and apply redundancy. 

The delay model for a TSV is discussed in the previous section. Process variation on its resistance and capacitance value causes uncertainty in signal transmission delay time. The delay for a cluster of TSVs fluctuates in a certain range. If the delay of a TSV is larger than a threshold, a switching signal cannot pass through it and this TSV is considered as failed. 

The first step of this BIST design is to find out the number of redundant TSVs needed. The design input is the process variation model of a TSV, which is based on the prior work by Wu et al.~\cite{Wu2011}.  Monte Carlo method is used to estimate the TSV defect rate. 
The modeling flow is shown in Algorithm~\ref{alg1}. An instance of a TSV cluster is created, and the delay value for each TSV is stochastically determined using the process variation model. Two neighboring TSVs are grouped together, and if any of them has a delay longer than a threshold, this group is marked as failed. The threshold value can be decided based on the test pulse frequency and also the strength of the driver. The total number of failed TSV groups is counted for this instance. The number of extra TSV groups needed to fix it is calculated by dividing the number of failed TSV group with the average TSV yield. 

The number of extra TSV group used for achieving a target cluster yield is determined by statistically analyzing the Monte Carlo simulation results. The simulation generates thousands of TSV cluster instances and records the number of TSV groups needed to be fixed. For example, if 3 redundant TSV groups are available, the instances with 3 or less defects can be fixed.  The yield after applying the redundancy is calculated, where the fixed instances are now considered as a good one. The number of extra TSV group keeps increasing until reaching the target yield. 

After determining the number of redundant TSV groups, the locations also need to be selected. The yield of a TSV is related to its location within the cluster. Prior work has shown that the TSVs at the edge of a cluster have lower yield comparing to the TSVs in the middle~\cite{Jing:IMEC}. The yield at the four corners are even worse. Our model considers this case by increasing the fluctuation range of R and C values for those TSVs locating at the edge of the array. These TSVs have a higher possibility to fail. The yield map from our model agrees with the experiment results from~\cite{Jing:IMEC}.

\SetAlFnt{\small}
\SetAlgoSkip{}
\begin{algorithm}[t]
\caption{Find Redundant TSV number}
\label{alg1}
\KwIn{TSV parameter variation model}
\KwOut{Number of extra TSV}
\For{i = 1 to instance\_number}
{Generate TSV delay map by TSV variation model\;
 \ForEach{TSV}
 {\If {delay $>$ threshold} 
 {mark as failed\;}
 }
 Group two TSVs, and find the group pass/fail map\; 
 Calculate failed\_group\_number\;
 $extra\_group\_need[i] =
 failed\_group\_number/redundant\_yield$\;
}
redundancy\_number = 0\;
\While{yield\_after\_fix $<$ target\_yield}
{redundancy\_number ++\;
\ForEach{instant[i]}{
\eIf {extra\_group\_need[i] $<=$ extra\_group\_number}
 {instant[i] = good\;}
 {instant[i] = failed\;}
}
update yield\_after\_fix\;
}
return (redundancy\_number)\;
\end{algorithm}

Figure~\ref{fig:map} shows an example of the location dependent TSV cluster yield, where the yield at the edge of the cluster is lower than that at the center. Two possible redundant TSVs placement methods are shown at the right side of the figure. One is to place them in a uniformly spacing array, and the other is to put them at the edges. In the second case, the redundant TSVs are placed at the low yield part, so that the normal TSVs use the high yield portion. This method saves test time, since the normal TSV yield is higher than the average yield and fewer test cycles are required. The disadvantage of placing redundant TSVs at the edges is that the distance between a failed TSV and its backup is larger comparing to a uniformly distributed redundant TSV array. The routing network that transfer the signal to its backup TSV may has long wire delay. 

After determining the amount of redundancy resources available, a BIST logic is designed to find and replace the failed TSV group with a good one. The first step is to find out the locations of those failed groups, if there is any. A breadth-first search algorithm is designed to perform this task, as shown in Algorithm~\ref{alg2}. Its inputs are the TSV cluster size and the number of redundant TSVs available. Its outputs are the location and the total number of the failed TSVs. The search algorithm measures a portion of the full test chain in one test cycle. If the result indicates that it contains failure groups, the portion of the chain under test is separated into two chains from the middle and test again. A First-In-First-Out (FIFO) queue is used to store the start and end positions of the section that need to be tested. It receives the indexes of such section and put them at the tail of the queue. For a data request, it sends out the first item at the head of the queue and removes it from the FIFO. 


\SetAlFnt{\small}
\SetAlgoSkip{}
\begin{algorithm}[t]
\caption{Breadth First Binary Search of TSV defects}
\label{alg2}
\KwIn{ The TSV cluster size N, extra TSV number}
\KwOut{Location of failed TSVs, number of failed TSV}
\ForEach{TSV clusters}{
current = [test\_chain\_start test\_chain\_end]\;
 \While{in\_test==1}
 {
 \If { check\_tsv\_chain(current) == fail}
 {
  \eIf {current\_start==current\_end}
   { add currend\_start to failed\_location\;
   failed\_number++\;}
  {
   first\_half = [current\_start (current\_start+current\_end)/2]\;
   push (first\_half) $=>$ FIFO\;
   second\_half=[(current\_start+current\_end)/2 current\_end]\;
   push (second\_half) $=>$ FIFO\;
  }
 }
\eIf {fifo is empty}
 {In\_test = 0\;}
 {current = pop(fifo)\;}
\If {(failed\_block $>$ extra\_tsv\_num) at current search level}
 {in\_test=0\;
 Set cannot fix\;}
 }
}
\end{algorithm}

The search begins by examining the full test chain. The variable $current$ in Algorithm~\ref{alg2} indicates the section under test in current cycle. It is set to cover the full chain during the first cycle. If the test result is good, no more action is required. If there is failed TSV groups in the chain, the indexes of the first half and the second half of the chain are pushed into the FIFO. In the subsequent cycles, the test block fetches one section from the FIFO and tests it. If this section failed, the test block repeats the previous separating and pushing operation again. 

Algorithm~\ref{alg2} has a $d*log(n)$ time complexity, where $d$ is the number of redundancy TSV. $n$ is the TSV cluster size. The search algorithm ends in two ways. One case is that it reaches a single TSV group and this group has defect. The location index of this failure point is recorded and the total failure number is increased by one. After all potential failure chain portion are examined, the FIFO is empty and the search finished. Another exit case is that the minimum number of failure points exceeds the number of redundancy resource available. The breadth-first search checks all possible failed section in one level then steps into the next level. If a section failed, it contains at least one failure TSV group. The minimum number of defects can be calculated by counting the number of failed section within a level. If there are more defects than the redundancy TSV groups, the cluster under test cannot be fixed and the test should be stopped. The size of the FIFO is determined by this ending condition. The maximum number of items in the FIFO is less than two times of the number of redundancy. 


\begin{figure}
\centering
\includegraphics[width=0.5\textwidth]{figure/tsv_yield_map}
\caption{\small{TSV yield map}}
\label{fig:map}
\end{figure}

